package seqlist;

/**
 * 带头(虚拟头节点)单链表
 * @author yuisama
 * @date 2022/04/21 19:15
 **/
public class LinkedListWithHead {
    private int size; // 当前链表中有效数据的个数(不包含头节点)
    // 实实在在存在的Node对象，不存储数据，就作为火车头
    private Node dummyHead = new Node();

    /**
     * 头插
     * @param val
     */
    public void addFirst(int val) {
        // 1
//        Node node = new Node();
//        node.val = val;
//        node.next = dummyHead.next;
//        dummyHead.next = node;
        // 2
//        Node node = new Node(val,dummyHead.next);
//        dummyHead.next = node;
        // 3
        dummyHead.next = new Node(val,dummyHead.next);
        size ++;
    }

    /**
     * 在索引为index的位置插入新元素val
     * @param index
     * @param val
     */
    public void add(int index,int val) {
        if (index < 0 || index > size) {
            System.err.println("add index illegal!");
            return;
        }
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        // 此时prev引用就是待插入位置的前驱
        // 1.
//        Node node = new Node();
//        node.val = val;
//        node.next = prev.next;
//        prev.next = node;
        // 2.使用构造方法在产生新节点的同时给node赋值以及链接后继节点
//        Node node = new Node(val,prev.next);
//        prev.next = node;
        // 3.使用匿名对象
        prev.next = new Node(val,prev.next);
        size ++;
    }

    /**
     * 删除单链表中索引为index位置的节点，返回删除前的节点值
     * @param index
     * @return
     */
    public int remove(int index) {
        // 1.索引合法性
        if (rangeCheck(index)) {
            Node prev = dummyHead;
            for (int i = 0; i < index; i++) {
                prev = prev.next;
            }
            Node cur = prev.next;
            prev.next = cur.next;
            int val = cur.val;
            cur.next = cur = null;
            size --;
            return val;
        }
        System.err.println("index illegal!");
        return -1;
    }

    public void removeAllValue(int val) {
        Node prev = dummyHead;
        while (prev.next != null) {
            if (prev.next.val == val) {
                prev.next = prev.next.next;
                size --;
            }else {
                prev = prev.next;
            }
        }
    }

    private boolean rangeCheck(int index) {
        if (index < 0 || index >= size) {
            return false;
        }
        return true;
    }

    public String toString() {
        String ret = "";
        for (Node x = dummyHead.next;x != null;x = x.next) {
            ret += x.val;
            ret += "->";
        }
        ret += "NULL";
        return ret;
    }
}